rtk 2014

2014.1.1 (preuredi vrstice)

Dnevnik

1. podnaloga

V računalniškem sistemu imamo zabeležene dogodke in bi jih radi v strnjeni obliki shranjevali v seznam nizov. Vsak dogodek (kot na primer prijava ali odjava uporabnika, razne napake) je predstavljen z nizom znakov (kratko besedilo/vrstica), dolžine največ $100$. Dogodki so zapisani v vhodni datoteki, po en dogodek v vsaki vrstici.

Ker se nekateri dogodki včasih zgodijo večkrat zapored (ne da bi se vmes zgodil kakšen drug dogodek), jih lahko shranimo v skrajšani obliki: ponovitve zadnjega shranjenega dogodka le štejemo. Ko se kasneje pojavi nek drugačen dogodek, shranimo le, da se je zadnji shranjen dogodek ponovil še $n$-krat. V primeru, da gre le za eno dodatno ponovitev ($n = 1$, torej skupaj s prvo izpisano pojavitvijo dve pojavitvi, glej zgled), namesto sporočila o ponovitvi shranimo kar sam ponovljeni dogodek, saj ne bi s sporočilom o ponovitvi nič prihranili.

Naloga

Napisana je funkcija strni_izpis(dat), ki naj bi brala dogodke iz vhodne datoteke in jih shranjevala v seznam nizov, ki ga na koncu vrne. Vendar pa so v funkciji pomešane vrstice. Zamenjaj vrstice in uredi zamike tako, da bo program deloval.

def strni_izpis(dat):
    """Funkcija sprejme tekstovno datoteko z zaporednimi dogodki,
       in jih strne tako, da napiše, kolikokrat se kateri ponovi."""
    prejsnja = ""
    return sez_strnjenih
    n = 0
    for dogodek in dat:
    sez_strnjenih.append("ponovljeno se %d-krat" % (n - 1))
    if n > 0 and prejsnja == dogodek:
    n += 1
    continue
    elif n == 2:
    sez_strnjenih.append("%s" % prejsnja[:-1])
    prejsnja = dogodek
    sez_strnjenih = []
    if dogodek:
    sez_strnjenih.append(dogodek.strip())
    with open(dat, 'r', encoding='utf-8') as dat:
    elif n > 2:
    n = 1

Vhodni podatki

Tekstovna datoteka dogodki.txt z zaporedjem dogodkov. Datoteka je kodirana v utf-8. Primer:

aaa
aaa
bbbbb
ccc
ccc
ccc
dd
dd
aaa
aaa
aaa
aaa

Izhodni podatki

Funkcija naj vrne seznam nizov, v katerem so strnjeni dogodki.

>>> strni_izpis(dogodki.txt)
['aaa', 'aaa', 'bbbbb', 'ccc', 'ponovljeno se 2-krat', 'dd', 'aaa', 'ponovljeno se 3-krat']

Uradna rešitev

def strni_izpis(dat):
    """Funkcija sprejme tekstovno datoteko z zaporednimi dogodki,
       in jih strne tako, da napiše, kolikokrat se kateri ponovi."""
    prejsnja = ""
    n = 0
    with open(dat, 'r', encoding='utf-8') as dat:
        sez_strnjenih = []
        for dogodek in dat:
            if n > 0 and prejsnja == dogodek:
                n += 1
                continue
            elif n == 2:
                sez_strnjenih.append("%s" % prejsnja[:-1])
            elif n > 2:
                sez_strnjenih.append("ponovljeno se %d-krat" % (n - 1))
            prejsnja = dogodek
            n = 1
            if dogodek:
                sez_strnjenih.append(dogodek.strip())
    return sez_strnjenih

2014.1.2 (preuredi vrstice)

Čopiči

1. podnaloga

V Ajdovščini tovarna Wlahna d. o. o. proizvaja krasne veganske bio čopiče, v celoti narejene iz lesa. Leseni ročaji so tako ali tako nekaj običajnega, v tej tovarni pa celó konico čopiča izdelajo iz lesa iste vrste, ki ga zmeljejo in predelajo v celulozna vlakna. V skladišču podjetja imajo lesene palčke enake debeline, a različnih dolžin, iz katerih želijo izdelati same enake čopiče. Za posamezen ročaj potrebujejo $r$ centimetrov lesa v enem kosu. Za konico čopiča pa potrebujejo toliko zmletega lesa, kot ga nastane iz $k$ centimetrov ene ali več palčk.

Naloga

Napisali so funkcijo koliko_copicev(k, r, l), ki ugotovi, koliko čopičev lahko podjetje s trenutno zalogo lesa lahko proizvede. Vendar pa so jih konkurenti čopičarji sabotirali in jim pomešali vrstice kode. Pomagaj jim tako, da zamenjaš vrstice v pravilen vrstni red in dodaš zamike.

def koliko_copicev(k, r, l):
    max_copicev = max_rocajev
    for palica in l:
    skup_dolzina = 0
    max_rocajev += palica // r
    skup_dolzina += palica
    if max_rocajev < max_copicev:
    max_rocajev = 0
    return int(max_copicev)
    max_copicev = skup_dolzina // (k + r)

Vhodni podatki

  r...dolžina palčke potrebne za en ročaj
  k...dolžina palčke potrebna za eno konico
  l...tabela dolžin palčk v cm

Izhodni podatki

Zaokroženo naravno število, ki predstavlja največje število čopičev, ki jih podjetje lahko proizvede.

Primer

>>> koliko_copicev(20, 4, [423, 116, 235, 13, 119, 60])
40

Uradna rešitev

def koliko_copicev(k, r, l):
    """Izračuna največje število čopičev, ki jih lahko proizvedemo glede na dolžino
    enega ročaja r, dolžino palčke k, potrebne za 1 konico, ter tabelo dolžin palčk."""
    skup_dolzina = 0
    max_rocajev = 0
    for palica in l:
        skup_dolzina += palica
        max_rocajev += palica // r
    max_copicev = skup_dolzina // (k + r)
    if max_rocajev <= max_copicev:
        max_copicev = max_rocajev
    return max_copicev

2014.1.3 (preuredi vrstice)

Pacifistični generali

1. podnaloga

Ker imajo vse svetovne vojaške velesile jedrsko orožje, ga moramo nujno imeti tudi pri nas v Sloveniji. Vlada je na IJS naročila izdelavo jedrskih konic, od Rusov pa so kupili bojno plovilo vnl-11 Triglav, kjer so smrtonosne rakete zdaj shranjene. Dostopa do tako uničujočega orožja ne sme imeti kdorkoli, ampak ga ima samo peščica najpomembnejših generalov.

Ker bi se lahko med generali našel norec, ki bi za zabavo poslal raketo ali dve na katero od sosednjih republik, so se na vojaškem ministrstvu odločili za stroge varnostne ukrepe. Naročili so izdelavo $k$ različic ključev za aktivacijo jedrskih konic. Ključi so oštevilčeni s števili od $1$ do $k$. Vsaka različica ključa je bila izdelana v več izvodih.

Te ključe so nato razdelili med $n$ generalov tako, da je vsak prejel neko podmnožico (samih različnih) ključev. Označimo z $G_i$ podmnožico ključev, ki jih ima $i$-ti general. Skupina generalov lahko sproži atomsko bombo, če imajo vsi skupaj vsaj po eno kopijo vsakega od ključev.

Na ministrstvu so pred kratkim opazili fenomen, na katerega pri snovanju sistema sploh niso pomislili. Med generali je vedno več pacifistov, ki niso pod nobenimi pogoji pripravljeni uporabiti jedrskega orožja. Vlada se zdaj boji, da bi lahko manjša skupinica pacifistov ostalim generalom preprečila uporabo orožja. Rekli bomo, da je sistem $r$-odporen, če nobena skupina $r$ (ali manj) generalov ne more ostalim preprečiti aktivacije jedrskih konic.

Naloga

Napisana je funkcija odpornost(r, k, [G1, ..., Gn]), katere cilj je, da za dani $r$ in dani sistem preveri, ali je ta sistem $r$-odporen. Funkcija pa ima pomešane vrstice. Zamenjaj vrstice tako, da bo funkcija dosegla željeno in dodaj zamike!

def odpornost(r, k, G):
    return True
    return False
    st_pojavitev[kljuc - 1] += 1
    for i in range(k):
    st_pojavitev = [0] * k
    for general in G:
    else:
    for kljuc in general:
    if st_pojavitev[i] <= r:

Vhodni podatki

Število $r$ predstavlja število pacifističnih generalov je potrebnih, da ne bodo mogli sprožiti jedrske rakete. Število $k$ predstavlja število ključev. V seznamu naborov $[G_1, ..., G_n]$ vsaka množica predstavlja ključe v lasti $i+1$-tega generala.

Omejitve vhodnih podatkov

Sistem ni večji od $10$ ključev in $10$ generalov.

Izhodni podatki

Funkcija vrne True ali False glede na to, ali je sistem $r$-odporen ali ne.

Primer

Recimo, da imamo $k = 3$ ključe in $n = 3$ generale. Naj bo

$G_1 = {1, 2}$
$G_2 = {2, 3}$
$G_3 = {1, 3}$

Prvi general ima torej ključ št. $1$ in ključ št. $2$. Drugi general ima ključ št. $2$ in ključ št. $3$. Tretji general ima ključ št. $1$ in ključ št. $3$. Vsak posamezni general ne more aktivirati jedrske konice, če pa se združita npr. prvi in drugi general, imata skupaj vse ključe.

$G_1 \cup G_2 = {1, 2, 3}$

Sistem iz zgleda je $1$-odporen, saj nobeden od generalov ne more sam 'blokirati' ostalih dveh.

Uradna rešitev

def odpornost(r, k, G):
    """Pove, ali je sistem ključev in generalov r-odporen ali ne."""
    st_pojavitev = [0] * k
    for general in G:
        for kljuc in general:
            st_pojavitev[kljuc - 1] += 1
    for i in range(k):
        if st_pojavitev[i] <= r:
            return False
        else:
            return True

2014.1.4 (preuredi vrstice)

Uniforme

1. podnaloga

Podjetje Wlahna d. o. o. se je odločilo svoje delavce obleči v praktične, trpežne uniforme iz debelega platna, skozi katerega jih ne bodo mogle bosti lesene trske, ki jih je v proizvodni hali podjetja vse polno. Uniforma sestoji iz treh kosov: hlač, jopiča in rokavic. Vsak kos uniforme je dobavljiv v velikostih od 1 do 100.

V podjetje je pravkar prispela nova pošiljka kosov uniform. Ko so jih razkladali s tovornjaka, so sproti popisali vsak kos uniforme (recimo: „hlače velikosti 73“). Zdaj jih zanima, koliko popolnih uniform lahko sestavijo. Popolna uniforma sestoji iz hlač, jopiča in rokavic v enaki velikosti.

Naloga

Napisana je funkcija stevilo_uniform(datoteka), ki naj bi prebirala podatke o razpoložljivih kosih uniforme in vrnila največje število popolnih uniform, ki se jih da sestaviti. Vendar pa so v programu pomešane vrstice. Zamenjaj vrstice in uredi zamike tako, da bo koda delovala!

def stevilo_uniform(vhod):
    zaloga = 100 * [0]
    velikost = int(podatek[1])
    zaloga[velikost - 1][oblacilo - 1] += 1
    for vrstica in vhodna:
    for i in range(100):
    podatek = vrstica.strip().split(' ')
    if len(podatek) > 1:
    oblacilo = int(podatek[0])
    for i in range(100):
    return max_uniform
    velikost = zaloga[i]
    max_uniform = 0
    max_uniform += min(velikost)
    zaloga[i] = 3 * [0]
    with open(vhod, 'r', encoding='utf-8') as vhodna:

Vhodni podatki

V prvi vrstici je zapisano število dostavljenih kosov $1 \leq n \leq 100$. Vsaka od naslednjih $n$ vrstic vsebuje dve števili ločeni s presledkom in opisuje posamezen kos uniforme. Prvo število ($1$, $2$, ali $3$) opisuje tip kosa (hlače, jopič, ali rokavice), drugo število (med $1$ in $100$) pa velikost.

15
3 98
1 45
1 74
1 45
2 98
1 45
2 45
1 74
2 74
2 98
2 74
3 74
3 74
1 98
2 74

Izhodni podatki

Največje število uniform, ki jih lahko sestavimo glede na zalogo. Za zgornje podatke:

>>> stevilo_uniform(zgornji_podatki):
3

Uradna rešitev

def stevilo_uniform(vhod):
    """Iz datoteke prebere podatke o zalogi ter poišče in vrne število popolnih uniform, ki jih lahko sestavimo."""
    zaloga = 100 * [0]   # različnih velikosti je 100
    for i in range(100):
        zaloga[i] = 3 * [0]
    max_uniform = 0
    with open(vhod, 'r', encoding='utf-8') as vhodna:
        for vrstica in vhodna:
            podatek = vrstica.strip().split(' ')
            if len(podatek) > 1:
                oblacilo = int(podatek[0])
                velikost = int(podatek[1])
                zaloga[velikost - 1][oblacilo - 1] += 1
    for i in range(100):
        velikost = zaloga[i]
        max_uniform += min(velikost)
    return max_uniform